home *** CD-ROM | disk | FTP | other *** search
- #ifndef __BTREEPAGE_H__
- #define __BTREEPAGE_H__
- /*
- * $RCSfile: BTREEPAGE.h,v $
- * $Revision: 1.1.1.1 $
- * $Date: 1996/05/04 21:55:07 $
- */
- /**********************************************************************
- * EXODUS Database Toolkit Software
- * Copyright (c) 1991 Computer Sciences Department, University of
- * Wisconsin -- Madison
- * All Rights Reserved.
- *
- * Permission to use, copy, modify and distribute this software and its
- * documentation is hereby granted, provided that both the copyright
- * notice and this permission notice appear in all copies of the
- * software, derivative works or modified versions, and any portions
- * thereof, and that both notices appear in supporting documentation.
- *
- * THE COMPUTER SCIENCES DEPARTMENT OF THE UNIVERSITY OF WISCONSIN --
- * MADISON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" CONDITION.
- * THE DEPARTMENT DISCLAIMS ANY LIABILITY OF ANY KIND FOR ANY DAMAGES
- * WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
- *
- * The EXODUS Project Group requests users of this software to return
- * any improvements or extensions that they make to:
- *
- * EXODUS Project Group
- * c/o David J. DeWitt and Michael J. Carey
- * Computer Sciences Department
- * University of Wisconsin -- Madison
- * Madison, WI 53706
- *
- * or exodus@cs.wisc.edu
- *
- * In addition, the EXODUS Project Group requests that users grant the
- * Computer Sciences Department rights to redistribute these changes.
- **********************************************************************/
-
- #include <stdio.h>
- #include <stdlib.h>
-
- #ifdef SERVER_MAKE
- # include <sys/types.h>
- # include <netinet/in.h>
- # include <setjmp.h>
- # include "sysdefs.h"
- #endif SERVER_MAKE
-
- #include "ess.h"
- #include "checking.h"
- #include "trace.h"
- #include "error.h"
- #include "io.h"
- #include "list.h"
- #include "object.h"
- #include "tid.h"
- #include "lock.h"
-
- #ifdef SERVER_MAKE
- # include "msgdefs.h"
- # include "thread.h"
- # include "semaphore.h"
- # include "latch.h"
- # include "pool.h"
- # include "link.h"
- #endif SERVER_MAKE
-
- #include "bf.h"
-
- #ifndef SERVER_MAKE
- # include "chunk.h"
- # include "load.h"
- # include "scan.h"
- # include "sm_params.h"
- # include "btree.h"
- # include "sm_globals.h"
- # include "sm_extfuncs.h"
- # include "sm_state.h"
- #endif SERVER_MAKE
-
- #include "bf_extfuncs.h"
- #include "bf_globals.h"
- #include "cc_macro.h"
- #include "volume.h"
- #include "lsn.h"
- #include "logrecs.h"
- #include "logaction.h"
- #include "trans.h"
- #ifndef SERVER_MAKE
- # include "clog.h"
- # include "clog_extfuncs.h"
- # include "loginfo.h"
- # include "clog_globals.h"
- #else
- # include "trans_extfuncs.h"
- # include "openlog.h"
- # include "log.h"
- # include "log_extfuncs.h"
- # include "thread_globals.h"
- # include "undo.h"
- # include "undo_extfuncs.h"
- # include "redo_extfuncs.h"
- # include "log_globals.h"
- #endif SERVER_MAKE
-
- #ifndef PFCDEFINED
- typedef int (*PFC)(int kLen1, void* kVal1, int kLen2, void* kVal2);
- typedef void (*PFK)(int kLen, char* kVal);
- #endif /* PFCDEFINED */
-
- #ifdef __ESS_H__
- #define ASSERT1(cond) SM_ASSERT(LEVEL_1, cond)
- #define ASSERT2(cond) SM_ASSERT(LEVEL_2, cond)
- #define ASSERT3(cond) SM_ASSERT(LEVEL_3, cond)
- #endif
-
-
- #include "bt_extfuncs.h"
-
- /*
- * Size of a BTREEPAGE defined in object.h
- */
-
- #ifdef __cplusplus /* BTREEPAGE defs for C++ only */
-
- const MAXINT = (1 << 31) - 1;
-
- //
- // This should be an external function in BF layer.
- //
- extern "C" PAGEHASH* BF_FindHashEntry(PID*);
-
-
- //
- // BT_TRACE macro
- //
- #ifdef BT_DEBUG
- #define BT_TRACE(x) printf x
- #else
- #define BT_TRACE(x)
- #endif
-
-
- //
- // Maximum # of levels
- //
- const MAXPARENTS = 10;
-
- const EMPTYSLOT = -1;
-
-
- enum BT_OPER {
- BT_READ = 1,
- BT_INSERT = 2,
- BT_DELETE = 4,
- BT_INSERT_DELETE = 6
- };
-
-
- //
- // BTREE page control structure
- //
- struct BTCONTROL {
- LRC lrc; // for recovery (MUST BE 1st FIELD (cheated))
- PID selfID; // id of this page
- TWO endData; // offset to end of the data section
- TWO numOffsets; // number of offsets
- TWO numFree; // number of free bytes
- UONE level; // leaf if 1, non-leaf if > 1
- ONE type; // SMDATATYPE
- SHORTPID next; // left sibling
- SHORTPID prev; // right sibling
- SHORTPID pid0; // first ptr in non-leaf nodes
- FOUR filler; // for 8byte alignment
- };
-
-
- const BT_MAGIC = 14021967;
-
- /*
- * BTREE page definition
- */
- const BT_DATASIZE = BTREE_PAGESIZE - sizeof(BTCONTROL);
-
- struct BT_Tuple;
-
- typedef TWO SLOT;
-
- class BTREEPAGE {
-
- //
- // Physical undos and redos must access page directly
- // (special _fr functions are used to bypass a g++ bug)
- //
- friend void undoBtree_fr(LOGRECORDHDR*);
- friend void redoBtree_fr(LOGRECORDHDR*);
-
- protected:
-
- BTCONTROL btCtrl; // control information
- char data[BT_DATASIZE - sizeof(SLOT)];
- SLOT slot[1]; // first slot on page
-
- void Compress();
-
- public:
- /*
- * General queries
- */
- LRC& lrc() { return btCtrl.lrc; }
- PID& SelfID() { return btCtrl.selfID; }
- int Level() { return btCtrl.level; }
- SHORTPID NextPage() { return btCtrl.next; }
- SHORTPID PrevPage() { return btCtrl.prev; }
- int Volume() { return btCtrl.selfID.volid; }
- SHORTPID FirstVector() { return btCtrl.pid0; }
- int NumSlots() { return btCtrl.numOffsets; }
- int IsLeaf() { return btCtrl.level == 1; }
- int IsNode() { return ! IsLeaf(); }
- SMDATATYPE KeyType() { return (SMDATATYPE) btCtrl.type; }
- IsSafe(BT_OPER oper, int maxKeyLen);
-
- /*
- * Space usage
- */
- UsableSpace() {
- return BT_DATASIZE - btCtrl.endData
- - (btCtrl.numOffsets * sizeof(slot[0]));
- }
- UsedSpace() { return BT_DATASIZE - btCtrl.numFree; }
- FreeSpace() { return btCtrl.numFree; }
-
- /*
- * Modify internal states
- */
- void SetFirstVector(SHORTPID pid) { btCtrl.pid0 = pid; }
- void SetLevel(int level) { btCtrl.level = level; }
- void Linkup(BTREEPAGE* rightPage, BTREEPAGE* rightRightPage);
-
- /*
- * Return a reference to tuple in slot sNum
- */
- BT_Tuple& Tuple(int sNum);
-
- /*
- * Add/Remove an element to/from slot sNum
- */
- AddElem(int sNum, const void* elem);
- RemoveElem(int sNum, const void* elem);
-
- /*
- * Search for keyVal and, if found, return the slot in retSlot.
- * Returns TRUE if found, FALSE otherwise.
- */
- Search(int keyLen, const void* keyVal, PFC compFunc, TWO& retSlot);
-
- /*
- * Insert/Remove a tuple into/from slot "slotNum"
- */
- void AppendTuple(BT_Tuple& tuple) {
- InsertTuple(tuple, NumSlots());
- }
- void InsertTuple(BT_Tuple& tuple, int slotNum);
-
- void RemoveTuple(int slotNum);
-
- /*
- * Move numTuples starting at slotNum to destSlot in destPage
- */
- void ShiftTuple(int slotNum, BTREEPAGE* destPage,
- int destSlot, int numTuples);
-
- /*
- * Set tuple to overflow (reclaim space used by oidList)
- */
- void SetOverflow(int slotNum, const PID& ovPid);
-
- /*
- * Set tuple to underflow (reinsert oidList)
- */
- void SetUnderflow(int slotNum, int oidCnt, const void* elList);
-
- //
- // Copy data and data usage indicators to target page
- //
- void CopyData(BTREEPAGE* target);
-
- //
- // Initialize a new page
- //
- void Init(const PID& pid, int level, SMDATATYPE keyType);
-
- //
- // Debugging utilities
- //
- CheckContent();
-
- void
- Print(BUFGROUP* bufGroup);
- };
-
- #if (defined DEBUG && defined btree_MODULE) || ! defined DEBUG
-
- INLINE BT_Tuple& BTREEPAGE::Tuple(int sNum)
- {
- return *((BT_Tuple*)(data+slot[-sNum]));
- }
-
- #endif /* (DEBUG && btree_MODULE) || !DEBUG */
-
-
- class ParentStack;
- class SMOPages;
- class OVPAGE;
-
- class LHINDPAGE;
- class LHDIRPAGE;
-
- //
- // REMEMBER: change GetPage() to call appropriate bf_ routine when it
- // is available. GetPage() should allocate a page in the buffer
- // without reading it from the server. It is called when the
- // program needs a page right after allocating it.
- //
- struct PageDesc {
- GROUPLINK* gLink;
-
- //
- // Implicit conversion operators
- //
- operator BTREEPAGE*() {
- return (gLink) ? (BTREEPAGE*) gLink->bufFrame : 0;
- }
- operator OVPAGE*() {
- return (gLink) ? (OVPAGE*) gLink->bufFrame : 0;
- }
- operator LHINDPAGE*() {
- return (gLink) ? (LHINDPAGE*) gLink->bufFrame : 0;
- }
- operator LHDIRPAGE*() {
- return (gLink) ? (LHDIRPAGE*) gLink->bufFrame : 0;
- }
-
- operator GROUPLINK*() { return gLink; }
- operator PAGEHASH*() { return gLink->pageHash; }
- operator ==(PageDesc& pd) { return pd.gLink == gLink; }
-
- int Read(BUFGROUP* bfg, const PID& pid, LOCKMODE lockMode);
- int GetPage(BUFGROUP* bfg, const PID& pid);
- void Force();
- void Dirty();
- void Unfix();
- void UnfixDirty();
- void UnfixUnlock();
- void UnfixUnlockDirty();
- PageDesc() { gLink = 0; }
- ~PageDesc() { };
- };
-
-
-
- #ifdef SERVER_MAKE
- inline int PageDesc::Read(BUFGROUP* bfg, const PID& pid, LOCKMODE )
- {
- SM_ASSERT(LEVEL_1, (gLink == 0));
- gLink = bf_ReadPage(bfg, &pid, BTREE_PAGE2SIZE, NOFLAGS);
- return (gLink) ? esmNOERROR : esmFAILURE;
- }
-
- inline int PageDesc::GetPage(BUFGROUP* bfg, const PID& pid)
- {
- // really read the page, do not use the NOREAD flag
- SM_ASSERT(LEVEL_1, (gLink == 0));
- gLink = bf_ReadPage(bfg, &pid, BTREE_PAGE2SIZE, NOFLAGS);
- return (gLink) ? esmNOERROR : esmFAILURE;
- }
- inline void PageDesc::Force()
- {
- }
- inline void PageDesc::Dirty()
- {
- DIRTY_PAGE(gLink->pageHash);
- }
- inline void PageDesc::Unfix()
- {
- SM_ASSERT(LEVEL_1, gLink != 0);
- bf_UnfixPage(gLink, BF_DEFAULT, FALSE);
- gLink = 0;
- }
- inline void PageDesc::UnfixDirty()
- {
- SM_ASSERT(LEVEL_1, gLink != 0);
- bf_UnfixPage(gLink, BF_DEFAULT, TRUE);
- gLink = 0;
- }
- inline void PageDesc::UnfixUnlock()
- {
- Unfix();
- }
- inline void PageDesc::UnfixUnlockDirty()
- {
- UnfixDirty();
- }
-
- #else
- inline int PageDesc::Read(BUFGROUP* bfg, const PID& pid, LOCKMODE lockMode)
- {
-
- SM_ASSERT(LEVEL_1, (gLink == 0));
- gLink = bf_ReadPage(bfg, &pid, H_INDEX, BTREE_PAGE2SIZE, lockMode);
- return (gLink) ? esmNOERROR : esmFAILURE;
- }
-
- inline int PageDesc::GetPage(BUFGROUP* bfg, const PID& pid)
- {
- SM_ASSERT(LEVEL_1, (gLink == 0));
- gLink = bf_FakeReadPage(bfg, &pid, H_INDEX, BTREE_PAGE2SIZE);
- return (gLink) ? esmNOERROR : esmFAILURE;
- }
-
- inline void PageDesc::Force()
- {
- bf_ForcePage(gLink->pageHash, NOFLAGS);
- }
- inline void PageDesc::Dirty()
- {
- bf_DirtyPage(gLink->pageHash);
- }
- inline void PageDesc::Unfix()
- {
- SM_ASSERT(LEVEL_1, gLink != 0);
- bf_UnfixPage(gLink, BF_LRU, FALSE);
- gLink = 0;
- }
- inline void PageDesc::UnfixDirty()
- {
- SM_ASSERT(LEVEL_1, gLink != 0);
- bf_UnfixPage(gLink, BF_LRU, TRUE);
- gLink = 0;
- }
- inline void PageDesc::UnfixUnlock()
- {
- SM_ASSERT(LEVEL_1, gLink != 0);
- bf_UnfixUnlockPage(gLink, BF_LRU, FALSE);
- gLink = 0;
- }
- inline void PageDesc::UnfixUnlockDirty()
- {
- SM_ASSERT(LEVEL_1, gLink != 0);
- bf_UnfixUnlockPage(gLink, BF_LRU, TRUE);
- gLink = 0;
- }
-
- #endif
-
-
- #include "BT_Tuple.h"
-
-
- #ifndef SERVER_MAKE
- extern BOOL btLogActive; // true if log should be generated
- extern BOOL btCLRLogActive; // true if CLR log should be generated during SMO
- #endif
-
- extern "C" {
- extern int BT_AllocPage(
- TID tid, int volume, BUFGROUP* bufGroup,
- PID& returnPid, TWO level, SMDATATYPE keyType);
- extern int BT_Traverse(
- const PID& rootPid, int keyLen, const void* keyVal,
- int& found, TWO& returnSlot, ParentStack& pl,
- BT_OPER oper, int maxKeyLen, PFC compFunc);
- extern int BT_SplitPage(
- TID tid, BUFGROUP* bufGroup, SMOPages* smo,
- ParentStack& pl, TWO slot,
- int length, PageDesc& rightLink);
- extern int BT_NewNodeTuple(
- TID tid, BUFGROUP* bufGroup, SMOPages* smo,
- ParentStack& pl, TWO klen,
- void* key, PID* subtreePid, PFC compFunc);
- extern int BT_ShiftTuples(
- BTREEPAGE* srcPage, int srcSlot,
- BTREEPAGE* destPage, int destSlot,
- int numTuples);
- extern int BT_SearchElemArray(
- int elSize, const void* el, int elCnt,
- const char* elArray, int& idx);
-
- extern int BT_LastEntry(
- const PID& rootPID, int& found,
- TWO& slot, ParentStack& pl);
- extern int BT_FirstEntry(
- const PID& rootPID, int& found,
- TWO& slot, ParentStack& pl);
-
- extern int BT_DecrElCnt(
- TID tid, const PID& rootPid, BUFGROUP* bufGroup,
- void* key, int keyLen, int maxKeyLen,
- PFC compFunc, LSNOFFSET undoNxtLSN);
- extern int BT_IncrElCnt(
- TID tid, const PID& rootPid, BUFGROUP* bufGroup,
- void* key, int keyLen, int maxKeyLen,
- PFC compFunc, LSNOFFSET undoNxtLSN);
- extern int BT_SetOverflow(
- TID tid, const PID& rootPid,
- BUFGROUP* bufGroup, void* key, int keyLen,
- int maxKeyLen, PFC compFunc, const void* elList,
- int numOid, LSNOFFSET undoNxtLSN);
- extern int BT_ResetOverflow(
- TID tid, const PID& rootPid,
- BUFGROUP* bufGroup, void* key, int keyLen,
- int maxKeyLen, PFC compFunc,
- const void* elList,
- int numOid, LSNOFFSET undoNxtLSN);
-
- extern int BT_SetCLR(TID tid);
- extern int BT_SetAnchor(TID tid);
- extern int BT_ElemDiff(int sz, const void* e1, const void* e2);
-
- extern void BT_LogPageInit(PAGEHASH* pHash,TWO level, SMDATATYPE keyType);
- extern void BT_LogModifyLink(
- PID&, PAGEHASH* pHash, LRC&,
- SHORTPID oldNext, SHORTPID newNext,
- SHORTPID oldPrev, SHORTPID newPrev,
- LSNOFFSET undoNxtLSN);
- extern void BT_LogModifyVector0(
- PID&, PAGEHASH*, LRC&, SHORTPID oldPid0,
- SHORTPID newPid0, LSNOFFSET undoNxtLSN);
- extern void BT_LogModifyLevel(
- PID&, PAGEHASH*, LRC&, TWO oldLevel,
- TWO newLevel, LSNOFFSET undoNxtLSN);
- extern void BT_LogLogicInsert(
- PID&, PAGEHASH*, LRC&, const PID& rootPid,
- const void* key, TWO keyLen,
- const void* el, TWO elSize,
- TWO maxKeyLen, TWO unique,
- SMDATATYPE keyType,
- LSNOFFSET undoNxtLSN);
- extern void BT_LogLogicDelete(
- PID&, PAGEHASH*, LRC&, const PID& rootPid,
- const void* key,
- TWO keyLen, const void* el, TWO elSize,
- TWO maxKeyLen, TWO unique, SMDATATYPE keyType,
- LSNOFFSET undoNxtLSN);
- extern void BT_LogLogicSetOverflow(
- PID&, PAGEHASH*, LRC&,
- const PID& rootPid,
- const void* key, TWO keyLen, TWO maxKeyLen,
- SMDATATYPE keyType, int numEl, int elSize,
- const void* elList, const PID& ovRoot,
- LSNOFFSET undoNxtLSN);
- extern void BT_LogLogicResetOverflow(
- PID&, PAGEHASH*, LRC&,
- const PID& rootPid,
- const void* key, TWO keyLen, TWO maxKeyLen,
- SMDATATYPE keyType, int numEl, int elSize,
- const void* elList, const PID& ovRoot,
- LSNOFFSET undoNxtLSN);
- extern void BT_LogLogicIncrElCnt(
- PID&, PAGEHASH*, LRC&,
- const PID& rootPid,
- const void* key, TWO keyLen, TWO maxKeyLen,
- SMDATATYPE keyType, LSNOFFSET undoNxtLSN);
- extern void BT_LogLogicDecrElCnt(
- PID&, PAGEHASH*, LRC&,
- const PID& rootPid,
- const void*key, TWO keyLen, TWO maxKeyLen,
- SMDATATYPE keyType, LSNOFFSET undoNxtLSN);
-
-
- #ifdef SERVER_MAKE
- extern void BT_LogPureCLR(LSNOFFSET);
- #endif
- }
-
- extern void BT_LogPhysicInsert(
- PID&, PAGEHASH*, LRC&,
- TWO slotNum, TWO numSlot, LSNOFFSET undoNxtLSN);
- extern void BT_LogPhysicDelete(
- PID&, PAGEHASH*, LRC&,
- TWO slotNum, TWO numSlot, LSNOFFSET undoNxtLSN);
-
- #ifdef SERVER_MAKE
- extern void BT_LogPhysicInsert(
- PID&, PAGEHASH*, LRC&, TWO slotNum,
- TWO numSlot, int length, void* p, LSNOFFSET undoNxtLSN);
- extern void BT_LogPhysicDelete(
- PID&, PAGEHASH*, LRC&, TWO slotNum,
- TWO numSlot, int length, void* p, LSNOFFSET undoNxtLSN);
- #endif
-
- #include "LHINDPAGE.h"
- #include "LHDIRPAGE.h"
-
- #endif /* #ifdef C++ */
-
- #endif __BTREEPAGE_H__
-
-
-